백준 12851번
오늘 풀어본 문제는 백준의 12851번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 $N$ $(0 \leq N \leq 100,000)$ 에 있고, 동생은 점 $K$ $(0 \leq K \leq 100,000)$ 에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 $X$ 일 때 걷는다면 $1$ 초 후에 $X-1$ 또는 $X+1$ 로 이동하게 된다. 순간이동을 하는 경우에는 $1$ 초 후에 $2*X$ 의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.
풀이과정
1번째 시도
예전에 숨바꼭질 문제를 풀어본 적이 있었기 때문에 코드를 조금만 수정하여 해결할 수 있을 것이라고 생각했다.
코드를 가져온 뒤 목적지에 도달하면 프로그램을 종료하는 대신 큐가 모두 빌 때까지 프로그램을 실행하면서 최단 거리와 그 가짓수를 저장하도록 하였다.
이 때 특정 숫자의 방문 여부를 저장하는 visited 변수로 인해 가짓수를 제대로 세지 못하여 사용하지 않도록 제거하였다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int N, K;
int shortest = INT_MAX;
int shortestCount = 0;
queue<pair<int, int>> q;
cin >> N >> K;
q.push({ N, 0 });
while (!q.empty()) {
pair<int, int> currentPoint = q.front();
q.pop();
cout << "Checking: (" << currentPoint.first << " " << currentPoint.second << ")\n";
if (currentPoint.second > shortest) {
continue;
}
else if (currentPoint.first == K) {
if (currentPoint.second < shortest) {
shortest = currentPoint.second;
shortestCount = 1;
}
else if (currentPoint.second == shortest) {
shortestCount++;
}
}
else {
if (currentPoint.first > 0) {
q.push({ currentPoint.first - 1 , currentPoint.second + 1 });
}
if (currentPoint.first < 100000) {
q.push({ currentPoint.first + 1 , currentPoint.second + 1 });
}
if (currentPoint.first <= 50000) {
q.push({ currentPoint.first * 2 , currentPoint.second + 1 });
}
}
}
cout << shortest << "\n";
cout << shortestCount;
return 0;
}
실행 결과 ‘출력 초과’ 가 발생하였다.
2번째 시도
또 어처구니 없는 실수를 하고 말았다. 테스트를 위해서 넣어둔 출력 코드를 제대로 지우지 않고 제출한 것이다.
코드는 다음과 같이 수정하였다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int N, K;
int shortest = INT_MAX;
int shortestCount = 0;
queue<pair<int, int>> q;
cin >> N >> K;
q.push({ N, 0 });
while (!q.empty()) {
pair<int, int> currentPoint = q.front();
q.pop();
if (currentPoint.second > shortest) {
continue;
}
else if (currentPoint.first == K) {
if (currentPoint.second < shortest) {
shortest = currentPoint.second;
shortestCount = 1;
}
else if (currentPoint.second == shortest) {
shortestCount++;
}
}
else {
if (currentPoint.first > 0) {
q.push({ currentPoint.first - 1 , currentPoint.second + 1 });
}
if (currentPoint.first < 100000) {
q.push({ currentPoint.first + 1 , currentPoint.second + 1 });
}
if (currentPoint.first <= 50000) {
q.push({ currentPoint.first * 2 , currentPoint.second + 1 });
}
}
}
cout << shortest << "\n";
cout << shortestCount;
return 0;
}
실행 결과 ‘메모리 초과’ 가 발생하였다.
3번째 시도
메모리 초과가 발생하는 이유로 바로 떠오른 것은 visited 변수를 이용하지 않은 것이었다. 이미 방문하여 다시 확인할 필요가 없는 수들까지 큐에 들어가면서 메모리 초과가 발생했다고 생각한 것이다.
우선 visited 변수를 다시 이용하도록 코드를 수정하면서, 최종 목적지를 탐색하는 경우는 visited 변수의 영향을 받지 않도록 조건문을 바꾸는 식으로 해결을 시도하였다.
코드는 다음과 같이 수정하였다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int N, K;
int shortest = INT_MAX;
int shortestCount = 0;
bool visited[100001] = { 0, };
queue<pair<int, int>> q;
cin >> N >> K;
q.push({ N, 0 });
visited[N] = true;
while (!q.empty()) {
pair<int, int> currentPoint = q.front();
q.pop();
if (currentPoint.second > shortest) {
continue;
}
else if (currentPoint.first == K) {
if (currentPoint.second < shortest) {
shortest = currentPoint.second;
shortestCount = 1;
}
else if (currentPoint.second == shortest) {
shortestCount++;
}
}
else {
if (currentPoint.first > 0 && (visited[currentPoint.first - 1] == false || currentPoint.first - 1 == K)) {
q.push({ currentPoint.first - 1 , currentPoint.second + 1 });
visited[currentPoint.first - 1] = true;
}
if (currentPoint.first < 100000 && (visited[currentPoint.first + 1] == false || currentPoint.first + 1 == K)) {
q.push({ currentPoint.first + 1 , currentPoint.second + 1 });
visited[currentPoint.first + 1] = true;
}
if (currentPoint.first <= 50000 && (visited[currentPoint.first * 2] == false || currentPoint.first * 2 == K)) {
q.push({ currentPoint.first * 2 , currentPoint.second + 1 });
visited[currentPoint.first * 2] = true;
}
}
}
cout << shortest << "\n";
cout << shortestCount;
return 0;
}
실행 결과 ‘틀렸습니다’ 가 떴다.
4번째 시도
왜 틀렸는지 고민을 해본 결과, 특정 지점에 가는 방식이 달라도 걸리는 시간이 동일할 수 있는데, 그런 경우의 수까지 제대로 세어주지 않아 이런 문제가 생긴다는 것을 알 수 있었다.
사실 그걸 고려하여 visited 변수를 사용하지 않으려고 한 것이었지만, 여전히 메모리 초과 문제로 인해 변수를 사용하는 수 밖에 없었다.
그래서 특정 visited 변수가 특정 지점에 도달한 적이 있는지와, 도달한 적이 있는 경우 걸린 시간을 저장하여 만약 기존에 도달한 적이 있는 지점이라 하더라도 시간이 같으면 다시 탐색을 진행하도록 하여 경우의 수를 제대로 셀 수 있도록 하였다.
코드는 다음과 같이 수정하였다.
#include <bits/stdc++.h>
using namespace std;
pair<bool, int> visited[100001];
int w[3] = { 1, 1, 2 };
int b[3] = { -1, 1, 0 };
bool isInRange(int position);
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int N, K;
int shortest = INT_MAX;
int shortestCount = 0;
queue<pair<int, int>> q;
cin >> N >> K;
q.push({ N, 0 });
visited[N] = make_pair(true, 0);
while (!q.empty()) {
pair<int, int> currentPoint = q.front();
q.pop();
if (currentPoint.second > shortest) {
continue;
}
else if (currentPoint.first == K) {
if (currentPoint.second < shortest) {
shortest = currentPoint.second;
shortestCount = 1;
}
else if (currentPoint.second == shortest) {
shortestCount++;
}
}
else {
for (int i = 0; i < 3; i++) {
int newPosition = w[i] * currentPoint.first + b[i];
if (isInRange(newPosition) && (visited[newPosition].first == false || newPosition == K || visited[newPosition].second == currentPoint.second + 1)) {
q.push({ newPosition , currentPoint.second + 1 });
visited[newPosition] = make_pair(true, currentPoint.second + 1);
}
}
}
}
cout << shortest << "\n";
cout << shortestCount;
return 0;
}
bool isInRange(int position) {
if (position < 0 || position > 100000) {
return false;
}
else {
return true;
}
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
예전에 비슷한 문제를 풀어봤기 때문에 쉽게 해결할 수 있을 거라고 생각했는데, 예상 외로 나를 당황시켰던 문제였다.
다행히 마지막으로 생각해낸 해결 방법이 잘 작동해서 망정이지, 떠올리지 못했더라면 더 오래 걸렸을지도 모르겠다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/12851